package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// tail 一直指向尾节点,也是临时节点, head 头结点
	var tail, head *ListNode
	// 位进值
	carry := 0
	for l1 != nil || l2 != nil {
		// 节点值默认是0
		n1, n2 := 0, 0
		if l1 != nil {
			// 节点值赋值
			n1 = l1.Val
			// 节点后移
			l1 = l1.Next
		}
		if l2 != nil {
			n2 = l2.Val
			l2 = l2.Next
		}
		// sum是求和后个位的值, carry是前一次求和的位进值
		sum := n1 + n2 + carry
		sum, carry = sum%10, sum/10
		// 用新的链表存储两个链表的和
		if head == nil {
			head = &ListNode{Val: sum}
			// 把tail的指向改成当前的节点
			tail = head
		} else {
			// 从第二个节点开始往尾节点增加元素
			tail.Next = &ListNode{Val: sum}
			tail = tail.Next
		}
	}
	// 最后一位的位进值加到链表最后
	if carry > 0 {
		tail.Next = &ListNode{Val: carry}
	}
	return head
}

func main() {
	l12 := ListNode{
		Val: 3,
	}
	l11 := ListNode{
		Val:  4,
		Next: &l12,
	}
	l1 := ListNode{
		Val:  2,
		Next: &l11,
	}

	l22 := ListNode{
		Val: 5,
	}
	l21 := ListNode{
		Val:  6,
		Next: &l22,
	}
	l2 := ListNode{
		Val:  4,
		Next: &l21,
	}
	addTwoNumbers(&l1, &l2)
}
